package com.learn.dataStructor.linked;

/**
 * @Author: Yinliu Hao
 * @Description:
 * @Date: Created in 2022/2/9 22:21
 * @Modify By:
 */
//约瑟夫斯链
public class JosephusLink {

    protected JosephusNode root;
    protected int count;

    public JosephusLink(){

    }

    public JosephusLink(JosephusNode root){
        this.root = root;
        root.next = root;
        this.count = 1;
        root.index =count;
    }

    //初始化约瑟夫环专用
    public JosephusLink(int count){
        for(int i=1;i<=count;i++){
            add(new JosephusNode(i));
        }
    }

    public void add(JosephusNode node){
        if(null == root){
            this.root = node;
            root.next = root;
            this.count = 1;
        }else{
            JosephusNode node1 = root;
            while(node1.next!=root){
                node1 = node1.next;
            }
            node1.next = node;
            node.next = root;
            count++;
        }
        node.index=count;
    }

    public void print(){
        System.out.println("count="+count);
        JosephusNode node = root;
        do{
            System.out.println(node.data+"/index:"+node.index);
            node = node.next;
        }while(node!=root);
    }

    public JosephusNode getAfterSeveral(JosephusNode node,int n){
        if(n==1){
            return node;
        }
        node = node.next;
        return getAfterSeveral(node,n-1);

    }

    //root阵亡后，上一个当rootb
    public void removeAfter(JosephusNode node) throws Exception{
        if(root==node.next){
            root = node;
        }
        node.removeAfter();
        count--;
    }

    public JosephusNode getByIndex(int n){
        return getAfterSeveral(root, n-1);
    }

    public static void main(String[] args) throws Exception{

        fun3();

    }

    public static void fun1() throws Exception{
        JosephusLink link = init();
        link.print();
        //node.print();
        System.out.println("-----------------");
        //node.removeAfter();
        //node.print();
        System.out.println("-----------------");
        //node.insertAfter(new JosephusNode("7"));
        //node.print();
    }

    public static void fun2(){
        JosephusLink link = new JosephusLink(10);
        link.print();
    }

    public static void fun3() throws Exception{
        JosephusLink link = new JosephusLink(10);
        link.removeAfter(link.getByIndex(10));
        System.out.println(link.root.data);
        }

    public static JosephusLink init(){
        JosephusLink link = new JosephusLink();
        link.add(new JosephusNode("1"));
        link.add(new JosephusNode("4"));
        link.add(new JosephusNode("6"));
        link.add(new JosephusNode("41"));
        link.add(new JosephusNode("55"));
        return link;
    }

}

class JosephusNode{
    Object data;
    JosephusNode next;
    int index;//增加每个节点在链表中的位置

    public JosephusNode(Object data,JosephusNode next){
        this.data = data;
        this.next = next;
    }

    public JosephusNode(Object data){
        this.data = data;
        this.next = null;
    }

    //这个add是加在后面，LinkNode的add是加在末尾。JosephusNode的add在不知道root的情况下无法加到末尾
    public void add(JosephusNode node){
        node.next = this.next;
        this.next = node;
    }

    public void removeAfter() throws Exception{
        if(this.next!=this){
            this.next=this.next.next;
        }else{
            throw new Exception("当前链表中只有一个节点");
        }
    }



 /*   public void insertAfter(JosephusNode node){
        node.next = this.next;
        this.next = node;
    }*/

    /*public void print(){
        System.out.println(this.data);
        if(null!=this.next){
            this.next.print();
        }

    }*/

}